package com.singzi.leetcode.jianzhiOffer;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
class Node1 {
    public int val;
    public Node1 left;
    public Node1 right;

    public Node1() {}

    public Node1(int _val) {
        val = _val;
    }

    public Node1(int _val,Node1 _left,Node1 _right) {
        val = _val;
        left = _left;
        right = _right;
    }
}
public class T0078 {
    public static void main(String[] args) {
        Node1 node1 = new Node1(4);
        Node1 node2 = new Node1(2);
        Node1 node3 = new Node1(5);
        node2.left = new Node1(1);
        node2.right = new Node1(3);
        node1.left = node2;
        node1.right = node3;
        Solution09 solution09 = new Solution09();
        solution09.treeToDoublyList(node1);
    }
}

class Solution09 {
    List<Node1> hashNode = new ArrayList<>();
    public Node1 treeToDoublyList(Node1 root) {

        midOrder(root);
        for(Node1 n:hashNode){
            System.out.println(n.val);
        }
        int n = hashNode.size();
        hashNode.get(0).left = hashNode.get(n - 1);
        hashNode.get(n - 1).right = hashNode.get(0);
        return hashNode.get(0);
    }

    public void midOrder(Node1 node){
        if(node.left != null) midOrder(node.left);
        hashNode.add(node);
        if(node.right != null) midOrder(node.right);

    }
}